package 力扣._131分割回文串;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

class Solution {
    // inter=[i,j,...,k] [i,,,j-1]为子序列
    void backtrack(String s, List<Integer> inter, int now, List<List<String>> list) {
        //1: 代表在0和1之间切开
        //剪枝： inter=[i,...,j,k]，若s[i,..,j-1]不是回文，则终止
        if (inter.size() > 1) {
            for (int i = inter.get(inter.size() - 2), j = inter.get(inter.size() - 1)-1; i < j; i++, j--)
                if (s.charAt(i) != s.charAt(j))
                    return;
        }
        //终止条件，判断下最后一段是不是回文
        if (now == s.length()) {
            for (int i = inter.get(inter.size() - 1), j = s.length()-1; i < j; i++, j--)
                if (s.charAt(i) != s.charAt(j))
                    return;
            inter.add(s.length());
            List<String> l = new LinkedList<>();
            System.out.println(inter);
            for (int i = 0; i < inter.size() - 1; i++) {
                l.add(s.substring(inter.get(i), inter.get(i + 1)));
            }
            list.add(l);
            inter.remove(inter.size()-1);
            return;
        }
        //回溯
        inter.add(now);
        backtrack(s, inter, now + 1, list);
        inter.remove(inter.size()-1);
        backtrack(s, inter, now + 1, list);
    }

    public List<List<String>> partition(String s) {
        //回溯，当前位置切不切
        List<Integer> inter = new ArrayList<>();
        inter.add(0);
        List<List<String>> list = new LinkedList<>();
        backtrack(s, inter, 1, list);
        return list;
    }

    public static void main(String[] args) {
        List<List<String>> aab = new Solution().partition("aab");
        System.out.println(aab);
    }
}